import java.util.Arrays;
import java.util.Scanner;
import java.util.Random;
public class Test2407mid {

    public static void main36(String[] args) {
        //给定一个有序整型数组, 实现二分查找
        int[] arr = {1,2,3,4,5,6,7,8,9};
        int key = 6,left = 0,right = arr.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(arr[mid]<key)
                left=mid+1;
            if(arr[mid]>key)
                right = mid-1;
            if(arr[mid]==key){
                System.out.println("根据二分查找,"+key+"的下标为"+mid);
                break;
            }
        }
    }
    public static void main35(String[] args) {
        //给定一个整型数组, 实现冒泡排序(升序排序)
        int[] arr = {9,8,7,6,5,4,3,2,1,0};
        int i;
        for(i = 0;i<arr.length-1;i++){
            int j;
            for(j = 0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void main34(String[] args) {
        //给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
        int[] arr = new int[]{1,3,2,4,3,9,3,2};
        int cou = 0;
        for(int i = 0;i<arr.length;i++){
            if(arr[i]%2==1)
                cou++;
            if(arr[i]%2==0)
                cou=0;
            if(cou>=3){
                System.out.println("true");
                break;
            }
        }
        if(cou<3)
            System.out.println("false");
    }
    public static void main33(String[] args) {
        //给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        //你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        int[] array = new int[]{2,3,3,3,4,3,2,4,3};
        Arrays.sort(array);
        //System.out.println(Arrays.toString(array));
        int i;
        int cou = 1;
        for(i = 0;i< array.length-1;i++){
            if(array[i]==array[i+1]){
                cou++;
                if(cou>array.length/2){
                    System.out.println(array[i]);
                    break;
                }
            }
            else
                cou =1;
        }
    }
    public static void main32(String[] args) {
        //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
        int[] arr ;
       arr = new int[]{2, 3, 2, 5, 3};
       int num = 0;
       for(int i = 0;i<arr.length;i++){
           num^=arr[i];
       }
        System.out.println(num);
    }
    public static void main31(String[] args) {
        /*给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
        你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
        你可以按任意顺序返回答案。*/
        int[] nums = {7,11,2,15};
        int target = 13;
        int i;
        for(i = 0;i<nums.length;i++){
            int j;
            for(j = i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target) {
                    System.out.println("[" + i + "," + j + "]");
                    break;
                }
            }
        }
    }
    public static void main30(String[] args) {
        //调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
        //如数组：[1,2,3,4,5,6]
        //调整后可能是：[1, 5, 3, 4, 2, 6]
        Scanner sc = new Scanner(System.in);
        int[] array = new int[]{1,2,3,4,5,6};
        int left = 0,right = array.length-1;
        while(left<right){
            if(array[left]%2!=0)
                left++;
            if(array[right]%2==0)
                right--;
            if(array[left]%2==0&&array[right]%2!=0&&left<right){
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    public static void transform(int[] a,int len){
        for(int i = 0;i<len;i++){
            a[i]*=2;
        }
        System.out.println(Arrays.toString(a));
    }
    public static void main29(String[] args) {
        /*实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 , 并设置到对应的数组元素上. 例如 原数组
        为 {1, 2, 3}, 修改之后为 {2, 4, 6}*/
        int[] arr = new int[]{1,2,3};
        transform(arr,arr.length);
    }
    public static void main28(String[] args) {
        //一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在 第10次落地时，共经过多少
        //米？第10次反弹多高？
        double height = 100;
        double sumHeight = height;
        int i;
        for(i = 1;i<=10;i++){
            height/=2;
            sumHeight+=2*height;
        }
        System.out.println("第10次落地时，共经过"+sumHeight+"米\n第10次反弹"+height+"米高");
    }
    public static int Peach(int day,int peach){//猴子摘桃方法
        if(day==0)
            return peach;
       return Peach(day-1,2*(peach+1));
    }
    public static void main27(String[] args) {
        /*猴子吃桃问题。猴子第一天摘下若干个桃子，当时就吃了一半，还不过瘾，就又吃了一个。第二天又将剩下的
桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第 10 天在想吃的时候就剩一个桃子了,
求第一天共摘下来多少个桃子*/
        int day = 10,peach = 1;
        int ret = Peach(day,peach);//1534
        System.out.println("第一天一共摘下来"+ret+"个桃子");
        for(int i = day;i>=1;i--){
            peach = (peach+1)*2;
        }
        System.out.println("第一天一共摘下来"+peach+"个桃子");
    }
    public static void main26(String[] args) {
        //编程求 1~10000 之间的所有“完全数”，完全数是该数的所有因子之和等于该数的数。例如，6 的因子有 1、2、
        //3，且 6=1+2+3，所以 6 是完全数。
        int i;
        for(i = 1;i<=10000;i++){
            int j,sum = 0;
            for(j = 1;j<i;j++){
                if(i%j==0)
                    sum+=j;
            }
            if(sum==i)
                System.out.print(i+" ");
        }

    }
    public static String myToString(int[] array) {
        String str = "[";
        int i;
        for(i = 0;i<array.length-1;i++){
            str +=array[i]+",";
        }
        str+=array[i]+"]";
        return str;
    }
    public static void main25(String[] args) {
        int[] array = {1,2,3,4};
        String ret = myToString(array);
        System.out.println(ret);
    }
    public static void main24(String[] args) {
        //编写程序，对输入的年、月、日，给出该天是该年的第多少天？
        //例如：2022年1月15日，是该年的第15天
        Scanner sc = new Scanner(System.in);
        int year = sc.nextInt(),mon = sc.nextInt(),day = sc.nextInt();
        int days = 0,sumDays = 0;
       int t = mon;
       for(mon = mon-1;mon>=1;mon--){
           if(mon == 1||mon==3||mon==5||mon == 7|| mon==8 ||mon == 10|| mon ==12){
               days = 31;
           }
           if(mon == 9||mon == 4||mon == 6||mon == 11 )
               days = 30;
           if(mon==2){
               if(year%400==0||(year%100!=0&&year%4==0))
                   days = 29;
               else
                   days = 28;
           }
           sumDays+=days;
       }
       sumDays+=day;
        System.out.println(year+"年"+t+"月"+day+"日是该年的第"+sumDays+"天");
    }
    public static void main23(String[] args) {
    //编写程序，输入一个字符，判断它是否为小写字母，如果是，将它转换成大写字母，否则，不转换
        Scanner sc = new Scanner(System.in);
        char alp = sc.next().charAt(0);
        if(alp>=97&&alp<=122){
            System.out.println(alp+"是小写字母");
            System.out.println(alp+"对应的大写字母是：");
            System.out.printf("%c",alp-32);
        }
        else{
            System.out.println(alp+"不是小写字母");
        }
    }
    public static int factorialSum(int N){
        int sum = 0;
        for(int i = 1;i<=N;i++){
            int s = 1;
            for(int j = 1;j<=i;j++){
                s *= j;
            }
            sum+=s;
        }
        return sum;
    }
    public static void main22(String[] args) {
        //求1！+2！+3！+4！+........+n!的和
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(factorialSum(n));
    }
    //在同一个类中定义多个方法：要求不仅可以求2个整数的最大值，还可以求3个小数的最大值？
    public static int maxNum(int n, int m){
        return n>m?n:m;
    }
    public static int maxNum(int n,int m,int l){
        int ret = maxNum(n,m);
        return ret>l?ret:l;
    }
    public static void main21(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(),m = sc.nextInt();
        int l = sc.nextInt();
        System.out.println(m+"和"+n+"中的最大值是"+maxNum(n,m));
        System.out.println(m+"、"+n+"和"+l+"这三个数中，最大的是"+maxNum(n,m,l));
    }
    public static int sum(int N){
        if(N==1)
            return 1;
        return N+sum(N-1);
    }
    public static void main20(String[] args) {
        //递归求 1 + 2 + 3 + ... + 10
        System.out.println(sum(10));
    }
    public static int factorial(int n){
        if(n==0)
            return 1;
        return n*factorial(n-1);
    }
    public static void main19(String[] args) {
        //递归求 N 的阶乘
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(factorial(N));
    }
    public static void solveHanNuoTa(int n,char src,char a,char dest){
        if(n == 1){
            System.out.println("把圆盘从"+src+"柱子移动到"+dest+"柱子");
            return;
        }
        //把n-1个圆盘从src柱子移动到a柱子，dest柱子作为辅助柱子
        solveHanNuoTa(n-1,src,dest,a);
        //把第n个圆盘（最下面的）直接从src柱子移动到dest柱子
        System.out.println("把圆盘从柱子"+src+"移动到柱子"+dest);
        //把剩下的n-1个圆盘从a柱子移动到dest柱子，src柱子作为辅助柱子
        solveHanNuoTa(n-1,a,src,dest);
    }
    public static void main18(String[] args) {
        //递归求解汉诺塔问题
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入圆盘数量：");
        int diskNum = sc.nextInt();
        char source = 'A';//起始柱子
        char auxiliary = 'B';//辅助柱子
        char destination = 'C';//目标柱子
        solveHanNuoTa(diskNum,source,auxiliary,destination);

    }
    public static int feiBoNaQi(int n){
        if(n==1||n==2)
            return 1;
        else
            return feiBoNaQi(n-1)+feiBoNaQi(n-2);
    }
    public static void main17(String[] args) {
        //递归求斐波那契数列的第 N 项
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int ret = feiBoNaQi(N);
        System.out.println(ret);
    }
    public static int Sum(int Num){
        int s =0;
        if(Num==0)
            return 0;
        s+=Num%10+Sum(Num/10);
        return s;
    }
    public static void main16(String[] args) {
        //写一个递归方法，输入一个非负整数，返回组成它的数字之和
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println(Sum(num));
    }
    public static void Print(int num){
        if(num<10){
            System.out.print(num+" ");
            return;
        }
        Print(num/10);
        System.out.print(num%10+" ");
    }
    public static void main15(String[] args) {
        //按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)（递归）
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        Print(num);
    }
    public static void main14(String[] args) {
        //输出一个整数的每一位，如：123的每一位是3，2，1
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        while(num!=0){
            System.out.println(num%10);
            num/=10;
        }
    }
    public static void main13(String[] args) {
        //获取一个数二进制序列中所有的偶数位和奇数位， 分别输出二进制序列
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println("奇数位的二进制序列：");
        for(int i = 30;i>=0;i-=2){
            System.out.print((num>>i)&1);
        }
        System.out.println();
        System.out.println("偶数位的二进制序列：");
        for(int i = 31;i>0;i-=2){
            System.out.print((num>>i)&1);
        }
    }
    public static void main12(String[] args) {
        /*编写代码模拟三次密码输入的场景。 最多能输入三次密码，密码正确，
        提示“登录成功”,密码错误， 可以重新输 入，最多输入三次。三次均错，则提示退出程序*/
        String code = "123456";
        int count = 3;
        Scanner sc = new Scanner(System.in);
        while(count>0){
            System.out.println("请输入密码：");
            String my_code = sc.nextLine();
            if(my_code.equals(code)) {
                System.out.println("登录成功");
                break;
            }
            else{
                count--;
                System.out.println("密码错误，还有"+count+"次机会");
            }
        }
    }
    /* public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    System.out.println(numSum(num));
    }

    public static int numSum(int num) {
        if(num<10)
            return num;
        return num%10+numSum(num/10);
    }*/
   /* public static void maxNUM(int a,int b, int c){
        int t;
        t = a>b?a:b;
        System.out.println(t>c?t:c);
    }
    public static void main(String[] args) {
        int a = 1,b = 2,c=3;
        maxNUM(a,b,c);
    }*/
    public static void main11(String[] args) {
        //完成猜数字游戏   ，用户输入数字，判断该数字是大于，小于，
        // 还是等于随机生成的数字，等于的时候退出程序
        Scanner sc = new Scanner(System.in);
        Random random = new Random();
        int randNum = random.nextInt(100);
        while(true){
            System.out.println("请输入要猜的数字:");
            int num = sc.nextInt();
            if(num<randNum)
                System.out.println("猜小了");
            else if(num>randNum)
                System.out.println("猜大了");
            else
            {
                System.out.println("猜对了");
                return;
            }
        }

    }
    public static void main10(String[] args) {
        //求出0～n之间的所有“水仙花数”并输出。(“水仙花数”
        // 是指一个三位数，其各位数字的立方和确好等于该数本 身，
        // 如；153＝1^3＋5^3＋3^3，则153是一个“水仙花数“。）
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入整数n，查找0~n之间的水仙花数：");
        int num = sc.nextInt();
        System.out.println("水仙花数有：");
        int i;
        for(i = 100;i<=num;i++){
            int temp = i;
            int j = 0,sum = 0;
            while(temp!=0){
                j = temp%10;
                temp/=10;
                sum+=j*j*j;

            }
            if(sum==i)
                System.out.println(i);
        }
        sc.close();
    }
    public static void main9(String[] args) {
        //给定一个数字，判定一个数字是否是素数
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int i = 0;
        for(i =2;i<=Math.sqrt(num);i++)
        {
            if(num%i==0){
                System.out.println(num+"不是素数");
                break;
            }
        }
        if(i>num)
            System.out.println(num+"是素数");
        sc.close();
    }
    public static void main8(String[] args) {
        //编写程序数一下 1到 100 的所有整数中出现多少个数字9
        int count = 0;
        for (int i = 1; i <= 100; i++) {
            int j = i;
            while (j != 0) {
                if (j % 10 == 9)
                    count++;
                j /= 10;
            }
        }
        System.out.println(count);
    }
    public static void main7(String[] args) {
        int i = 3;
        for(i = 3;i<100;i++){
            if(i%3!=0||i%6!=0) {
                continue;
            }
            System.out.println(i);
        }
    }
    public static void main6(String[] args) {
        int a = 3;
        int b =4;
        System.out.println("a=="+a+" b=="+b);
        System.out.println("a+b == "+(a+b));
    }
    public static void main5(String[] args) {
        byte a = (byte)128;
        System.out.println(a);//-128
        byte a2 = (byte)129;
        System.out.println(a2);//-127

        int a3 = 10;
        long a4 = 20;
        int b = (int)(a3+a4);
        long c = a3+a4;
        System.out.println(b);
        System.out.println(c);

        byte a5 = 10;
        byte a6 = 40;
        int sum = a5 + a6;
        byte sum2 = (byte)(a5+a6);
        System.out.println(sum);
        System.out.println(sum2);
    }
    public static void main4(String[] args) {
        boolean flag = false;//只能为true或false，不是0和1
        System.out.println(flag);

        String str = "Hello ";
        String str2 = "Kiku";
        System.out.println(str+str2);//输出有三种方式，printf(),println,print
        System.out.println("haha"+10+20);//haha1020
        System.out.println("haha"+(10+20));//haha30
        System.out.println(10+20+"haha");//30haha

        //整数转字符串
        int a = 123;
        String ret = a+"";//法1
        System.out.println(ret);
        String ret2 = String.valueOf(a);//法2
        System.out.println(ret2);
    }
    public static void main3(String[] args) {
        float f = 3.14f;
        System.out.println(f);

        char ch = 'a';//char类型占两个字节
        System.out.println(ch);
        char ch2 = '哈';
        System.out.println(ch2);
        char ch3 = 'A' + 32;
        System.out.println(ch3);
        char ch4 = 66;
        System.out.println(ch4);
    }
}
